Quan Vũ người Giải Lương, quận Hà Đông (nay là Vận Thành, tỉnh Sơn Tây). Tam Quốc ngoại truyện cho rằng ông là người Bồ châu.[3]

Tiểu thuyết Tam Quốc Diễn Nghĩa mô tả nhân vật Quan Vũ cao chín thước (hơn 2 mét ngày nay), mặt đỏ như gấc, mắt phượng mày tằm, râu dài hai thước, oai phong lẫm liệt. Những miêu tả này của La Quán Trung chỉ là ước lệ, và không có cơ sở lịch sử.Quan Đế minh thánh kinh cho rằng cụ nội Quan Vũ là Quan Long Phùng, ông nội Quan Vũ là Quan Thẩm (關審), tự là Vấn Chi (問之); cha ông là Quan Nghị (關毅), tự là Đạo Viễn (道遠).[4] Các sách sử chính thống không có ghi chép gì về tổ tiên của Quan Vũ.

Thời trẻ, Quan Vũ làm nghề bán đậu phụ. Tuy nhà nghèo, ông cũng được theo học cả văn lẫn võ.[5] Ông là người vũ dũng, hào hiệp, ghét kẻ ác, thường bênh vực người yếu. Do bênh vực người khác mà ông phạm tội giết người, phải bỏ quê hương đến nương náu ở quận Trác.

Tại quận Trác, Quan Vũ đã gặp gỡ và trở nên thân thiết với Lưu Bị và Trương Phi. Ba người coi nhau như anh em.

Tiểu thuyết Tam Quốc Diễn Nghĩa có tình tiết hư cấu về việc Lưu, Quan, Trương kết nghĩa huynh đệ ở vườn đào, xin được chết cùng ngày, cùng tháng, cùng năm, Lưu Bị nhiều tuổi nhất nên là anh cả, kế đến là Quan Vũ. Thực tế sử sách không ghi chép về việc 3 người đã làm lễ kết nghĩa, mà chỉ ghi rằng 3 người có quan hệ rất thân thiết. Sử sách cũng không ghi chép về năm sinh của Quan Vũ nên không rõ ông ít tuổi hay nhiều tuổi hơn Lưu Bị.